package hash;

import java.util.NoSuchElementException;

/**
 * 基于开散列方案下的哈希表实现
 * @author yuisama
 * @date 2022/03/13 15:28
 **/
public class MyHashMap {
    private class Node {
        // 对key求哈希运算
        int key;
        int value;
        Node next;
        public Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    // 当前哈希表中实际存储元素的个数
    private int size;
    // 默认哈希表的长度
    // 也有的教科书，将每个哈希表的数组元素称为哈希桶
    private static final int DEFAULT_CAPACITY = 16;
    // 默认负载因子
    private static final double LOAD_FACTOR = 0.75;
    // 取模数，用于取得key的索引
    private int M;
    // 实际存储数据的数组
    private Node[] data;

    public MyHashMap() {
        this(DEFAULT_CAPACITY);
    }

    public MyHashMap(int initCap) {
        this.data = new Node[initCap];
        this.M = initCap;
    }

    // 哈希函数
    public int hash(int key) {
        return Math.abs(key) % M;
    }

    // 在当前的哈希表添加一个键值对 key = value
    public int add(int key,int value) {
        // 1.先对key取模,得到存储的索引
        int index = hash(key);
        // 2.遍历这个索引对应的链表，查看当前的key是否已经存在了
        for (Node x = data[index];x != null;x = x.next) {
            if (x.key == key) {
                // 此时key已经存在，更新value
                int oldVal = x.value;
                x.value = value;
                return oldVal;
            }
        }
        // 3.此时key对应的元素在当前的哈希表中不存在，新建节点头插哈希表中
        Node node = new Node(key,value,data[index]);
        data[index] = node;
        size ++;
        // 4.添加一个新元素后，查看是否需要扩容
        if (data.length * LOAD_FACTOR <= size) {
            resize();
        }
        return value;
    }

    /**
     * 哈希表扩容
     */
    private void resize() {
        // 新数组长度变为原来的一倍
        Node[] newData = new Node[data.length << 1];
        // 原节点的key对应新数组的索引hash
        // 现在的取模数应该变为新数组的长度
        this.M = newData.length;
        // 遍历原数组,进行节点的搬移
        for (int i = 0; i < data.length; i++) {
            if (data[i] != null) {
                // 对应的链表不为空
                // 进行对应的链表遍历
                for (Node x = data[i];x != null;) {
                    // 暂存一下后继节点
                    Node next = x.next;
                    int newIndex = hash(x.key);
                    // 新数组的头插
                    x.next = newData[newIndex];
                    newData[newIndex] = x;
                    // 继续进行下一个节点的搬移操作
                    x = next;
                }
            }else {
                // 当前数组i对应的索引下，没有节点
                continue;
            }
        }
        data = newData;
    }

    /**
     * 删除哈希表中key对应的节点
     * 返回删除前的value
     * @param key
     * @return
     */
    public int remove(int key) {
        int index = hash(key);
        // 判断头节点是否是待删除的节点
        Node head = data[index];
        if (head.key == key) {
            int val = head.value;
            data[index] = head.next;
            head.next = head = null;
            size --;
            return val;
        }
        // 当前链表的头节点不是待删除的节点
        Node prev = head;
        while (prev.next != null) {
            if (prev.next.key == key) {
                // perv恰好是待删除节点的前驱
                Node cur = prev.next;
                int val = cur.value;
                prev.next = cur.next;
                cur.next = cur = null;
                size --;
                return val;
            }
            prev = prev.next;
        }
        throw new NoSuchElementException("no such key!remove error!");
    }

    public boolean containsKey(int key) {
        int index = hash(key);
        // 遍历index位置对应的链表，查看是否有节点的key与查询的key相等
        for (Node x = data[index];x != null;x = x.next) {
            if (x.key == key) {
                return true;
            }
        }
        return false;
    }

    public boolean containsValue(int value) {
        // 遍历整个哈希表
        for (int i = 0; i < size; i++) {
            for (Node x = data[i];x != null;x = x.next) {
                if (x.value == value) {
                    return true;
                }
            }
        }
        return false;
    }
}